package 剑指offer;

import java.util.HashMap;
import java.util.Scanner;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:47:08 
* @Description：
* 
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），
返回结果为复制后复杂链表的head。
（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
*/


class RandomListNode{
	int label;
	RandomListNode next=null;
	RandomListNode random=null;
	
	RandomListNode (int label){
		this.label=label;
	}
}
public class A25复杂链表的复制 {
	

	
	//有问题
	
	
		/*
		*解题思路：
		*1、遍历链表，复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
		*2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
		*3、拆分链表，将链表拆分为原链表和复制后的链表
		*/
	public static RandomListNode Clone(RandomListNode pHead) {
		if (pHead==null) {
			return null;
		}
		RandomListNode currentNode = pHead;
		
		//1.复制每个结点，如复制结点A得到A1，将结点A1插入到结点A后面
		while (currentNode!=null) {
			
			RandomListNode cloneNode = new RandomListNode(currentNode.label);
			RandomListNode nextNode = currentNode.next;
			currentNode.next = cloneNode;
			cloneNode.next=nextNode;
			currentNode=nextNode;
		}
		
		currentNode=pHead;
		
		//2.重新遍历链表，复制老结点的随机指针给新结点，
		//如A1.random=A.random.next
		while (currentNode!=null) {
			currentNode.next.random=currentNode.random==null?null:currentNode.random;
			currentNode=currentNode.next.next;
		}
		
		//3.拆分链表，将链表拆分为原先的链表和复制出来的链表
		currentNode=pHead;
		RandomListNode pCloneHead = pHead.next;
		while (currentNode!=null) {
			RandomListNode cloneNode = currentNode.next;
			RandomListNode next = cloneNode.next;
			cloneNode.next=cloneNode.next==null?null:cloneNode.next.next;
		}
		return pCloneHead;
	}
     
	
	//用一个 hashmap 建立新旧链表节点的对应的结点关系
	//迭代旧链表，从而在 hashmap 中更新新链表的 next 与 random 两个字段
	public static  RandomListNode Clone11(RandomListNode pHead) {
		if (pHead==null) {
			return null;
		}
		
		RandomListNode p1 = pHead;
		RandomListNode p2 = pHead;
		
		HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
		while (p1!=null) {
			map.put(p1, new RandomListNode(p1.label));
			p1=p1.next;
		}
		
		while (p2!=null) {
			if (p2.next!=null) {
				map.get(p2).next=map.get(p2.next);
			}else {
				map.get(p2).next=null;
			}
			
			map.get(p2).random=map.get(p2.random);
			p2=p2.next;
		}
		return map.get(pHead);
	}
	
	public static void main(String[] args) {
		Scanner scan=new Scanner(System.in);
        String[] array=scan.nextLine().split(" ");
        RandomListNode Head=new RandomListNode(Integer.parseInt(array[0]));
        RandomListNode nextNode=Head;
        for(int i=1;i<array.length;i++){
            RandomListNode newNode=new RandomListNode(Integer.parseInt(array[i]));
            nextNode.next=newNode;
            nextNode=newNode;
        }
        RandomListNode cloneMap = Clone11(Head);
        while (cloneMap!=null) {
			System.out.print(cloneMap.label+" ");
			cloneMap=cloneMap.next;
		}
//        
//        RandomListNode cloneNew = Clone(Head);
//        while (cloneNew!=null) {
//			System.out.print(cloneNew.label+" ");
//			cloneNew=cloneNew.next;
//		}
        
        
	}

}
